package offer;

import java.util.ArrayList;
import java.util.List;

public class Offer17 {

    public void print1ToMaxOfNDigits(int n) {

        int  pow =(int) Math.pow(10, n);
        for (int i = 1; i <=pow-1 ; i++) {
            System.out.println(i);
        }
    }




////存放结果
//  List<List<Integer>> result = new ArrayList<>();
//  //暂存结果
//          List<Integer> path = new ArrayList<>();
//
//  public List<List<Integer>> permuteUnique(int[] nums) {
//    boolean[] used = new boolean[nums.length];
//    Arrays.fill(used, false);
//    Arrays.sort(nums);
//    backTrack(nums, used);
//    return result;
//  }
//
//  private void backTrack(int[] nums, boolean[] used) {
//    if (path.size() == nums.length) {
//      result.add(new ArrayList<>(path));
//      return;
//    }
//    for (int i = 0; i < nums.length; i++) {
//      // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
//      // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
//      // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
//      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
//        continue;
//      }
//      //如果同⼀树⽀nums[i]没使⽤过开始处理
//      if (used[i] == false) {
//        used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
//        path.add(nums[i]);
//        backTrack(nums, used);
//        path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
//        used[i] = false;//回溯
//      }
//    }
//  }
//     List<Integer> path = new ArrayList<>();

   StringBuffer  path= new  StringBuffer();
    int count=0;
    public void print1ToMaxOfNDigits1(int n) {
        int  pow =(int) Math.pow(10, n);
        int[] result=new int[pow-1];
        backtracking(result,n);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    void   backtracking(int[]  result,int n){
        if (path.length()==n){
            String s = path.toString();
//            System.out.println(s);
            if (Integer.valueOf(s)!=0){
                result[count++]=Integer.valueOf(s);
            }
           return;
        }
        for (int i = 0; i <=9; i++) {
            path.append(i);
            backtracking(result,n);
            path.deleteCharAt(path.length()-1);
        }

    }

    public static void main(String[] args) {
        Offer17 offer17 = new Offer17();
        offer17.print1ToMaxOfNDigits1(1);
    }





}
